#define _CRT_SECURE_NO_WARNINGS 1

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(nullptr), right(nullptr) {
	}
};
class Solution {
public:
	void _Convert(TreeNode* root, TreeNode*& prev)
	{
		if (root == nullptr)
		{
			return;
		}
		_Convert(root->left, prev);
		root->left = prev;
		if (prev)
		{
			prev->right = root;
		}
		prev = root;
		_Convert(root->right, prev);
	}
	TreeNode* Convert(TreeNode* pRootOfTree)
	{
		if (pRootOfTree == nullptr) return nullptr;
		TreeNode* ret = pRootOfTree;
		while (ret->left)
		{
			ret = ret->left;
		}
		TreeNode* prev = nullptr;
		_Convert(pRootOfTree, prev);
		return ret;
	}
};
